| Python 递归 深入理解递归 Python递归剖析，绝对让你看懂！ | 您所在的位置：网站首页 › 看懂python 代码需要多久 › Python 递归 深入理解递归 Python递归剖析，绝对让你看懂！ |
Python 递归 深入理解递归 Python递归剖析，绝对让你看懂！
|
目录
递归剖析 递归的两个过程 return 返回值 详解
递归思路二分法和递归尾递归递归练习题
递归剖析
递归真的很重要，之前学的时候，学的一知半解，以为真正了解，每次想到递归，就记得一句：返回给函数的调用者，嗯？函数调用者，你是说外部，还是内部啊？疑问太多了，还有就是被告知一句：递归能解决的问题，循环都能解决，所以就更加不重视递归了！直到接触算法后，在解决问题时，最快，最容易理解的解法就是递归，但是此时的递归却是看不太懂为什么要这样做！我先来说下，在算法中遇到可以用递归轻松完成的：希尔排序、归并排序、快速排序、反转链表及各种反转问题、二叉树的深度遍历、二叉树的各种题基本可以用、全排列…还有算法步骤里需要用到，太多了，所以，递归非常重要！“To iterate is human, to recurse divine 迭代是人，递归是神”，接下来，我也是看了很多算法书和视频，重点来整理下递归！
递归的两个过程
首先“递归”包括两个过程：递“去”的过程，“归”回的过程！先从一个简单的递归函数讲起
def di_gui(n):
print(n, "")
if n > 0:
di_gui(n - 1)
print(n, '')
di_gui(5) # 外部调用后打印的结果是？
递归的执行过程：首先，递归会执行“去”的过程，只需要满足终止条件，就会一直在函数内，带着更新的参数，调用函数自身，注意：到内部调用函数， 以下面的代码不会被执行，而是暂停阻塞；此时 随着函数每调用一次自身，还没有触发 返回值和到达终止条件，等同于在原来的基础上不断“向下/向内”开辟新的内存空间，记住，每次调用一次函数，就不是处在同一空间（想象下《盗梦空间》里的情景，梦中梦，都是处于不同的空间） 什么时候“递”去的过程结束？记住有两种情况>>> 一是：当前这层空间函数全部执行结束（终止条件），二是：执行到了return 返回值，直接返回； 重点来理解下，首先是一，看上面的列子，例子中没有return，但是不断的调用后，最终还是停止了，因为最后n=0时，di_gi(0)还是去调用，从上往下执行时，遇到if n>0 它被终止了，走不下去了，表明，自己能到达的这层空间已经全部执行完毕；接下来请原地返回吧，返回到哪里？返回到函数的调用者，好我们返回到 di_gui(0)，把“到内部调用函数” 以下的代码全部执行完；执行完，看代码走到末尾，以为走出了最外层函数？注意了，此时它所处的空间并不是最外层哦，因为之前它被调用就在空间里面，所以回到的是 di_gui(1)的这一层空间，现在才是真正的开始“回”，所以继续把di_gui(1)的这一层空间，“到内部调用函数”以下的代码全部执行完，回到di_gui(2)的这一层空间…直到到达最开始 从外部调用，让参数5进入的最外层空间位置，才走出来！表示《盗梦空间》里，柯布醒了！ 从内存角度（本质）来分析：每调用一次函数，都会单独开辟一份栈帧空间，递归函数就是不停的开辟和释放栈帧空间的过程，具体来理解下：一个普通函数从执行到结束，就是一个开辟空间和释放空间的过程；而递归函数是在调用最外层函数时，先开辟一个最外层空间，每调用一次自身，就会在最外层空间内，再自己开辟本次的空间（所以递归耗内存）（还有一种说法是，不断的本次空间的基础上再开辟空间，等于是不断的嵌套，其实这两种说法本质上是一样的，因为信息都可以做到不共享），空间之间如果不通过参数传递或者用return 返回值，信息是不共享的，如下图↓↓↓
递归的数据共享情况：递归每一层间的数据是独立的，不共享，但是可以通过参数或者返回值来形成共享，参数具体在传入的是“引用类型”（比如列表） 递归 必须要有一个出口，如果没有出口就会重复调用，不断的开辟栈帧空间 # 获取最大递归层数： import sys res=sys.getrecursionlimit() print(res) # 结果：1000 # sys.setrecursionlimit(800) 可以自己设置最大递归层数 解释含有 return 返回值的递归，记住 return的返回流程是：先计算，再返回 ，来看下一段求阶乘的代码： def jie_cheng(n): if n 2: get_num(num - 1) print(num) get_num(4) # 输出结果为：2 3 4
代码变化一下： def get_num(num): if num > 2: get_num(num - 1) else: print(num) get_num(4) # 输出结果为 2 ''' 解析一下：加了else后，首先代码区有两个分支， 在num>2时，执行会有递归，当n=4 是开辟一层空间； n=3时开辟一层空间，此时 get_num(2) 再开辟一个空间， 当它从上往下执行过程中，在他本层空间遇到if num>2 不成立，所以走分支 else，直接打印出来； 此时代码还没结束，回到上一层空间，num=3, num>2 已经进入了if 不会走else， num=4 也不会走else，所以这两层空间没有值输出！ ''' return 返回值 详解 上面这一大部分，就算是递归入门了，接下来才刚刚开始哦！还要继续讲 return ；先来看下这几段代码：求全排列的一部分递归代码，试着分别写出运行结果，并依次分析原因↓↓↓ # 例1： def fullpermutation(list): if list is None: return None if len(list) == 1: return [list] res = [] pivot = list[0] remain = fullpermutation(list[1:]) print(remain) print(fullpermutation([1, 2, 3])) ''' 输出结果为： [[3]] None None ''' 递归只会在两种情况下触发“回”的过程，上述是在最后一层空间是碰到了return，所以给回到它的调用处（阻塞处），因为return会给调用者返回一个值，所以在本层空间，remain接收到了一个值：[[3]]；接着执行下面的代码，即是打印remain，所以输出“[[3]]”，执行完print，等于回到了上一层空间，又到了调用处（阻塞处），那么这层空间还有返回值吗？答案是没有，所以“最后一层空间是碰到了return 给它返回的值 只会给最后一层使用”，所以接下来两层都是打印空！ # 例2： def fullpermutation(list): if list is None: return None if len(list) == 1: return [list] res = [] pivot = list[0] return fullpermutation(list[1:]) print(fullpermutation([1, 2, 3])) ''' 输出结果为： [[3]] ''' 这次是，在最后一层返回时，获得了一个返回值 [[3]] ，然后回到上一层时，前面又有return 表示需要把本层的返回值，返回到上层的接收处，重复，直到回到最外层，这个从底层传上来的返回值，一直传到了最外层，所以才打印出来的，只有最后一层，但是每次一层都获得了返回值，和例子1 后面两层没有返回值是不同的哦！ # 例3： def fullpermutation(list): if list is None: return None if len(list) == 1: return [list] res = [] pivot = list[0] remain = fullpermutation(list[1:]) print(list) print(fullpermutation([1, 2, 3])) ''' 输出结果为： [2, 3] [1, 2, 3] None ''' 最后一层碰到return，触发会的过程，回到调用处，执行阻塞处下面的代码，打印list，这个list是什么？它就是本层空间 参数的规模（因为代码写的是规模不断变小从[1,2,3]>>>[2,3]>>>[3]）,显然，从最后一层回到上一层，此时规模是[2,3]，所以打印list 就是[2, 3]；接着继续回到上一层，即是最外层，规模是[1,2,3]，所以打印[1, 2, 3]，最后的None是因为最外层函数，没有返回值，所以才打印出None # 例4： def fullpermutation(list): if list is None: return None if len(list) == 1: return [list] res = [] pivot = list[0] remain = fullpermutation(list[1:]) return list print(fullpermutation([1, 2, 3])) ''' 输出结果为： [1, 2, 3] ''' 依照上面的步骤，触发回的过程，只要没有到达最外层，return list 返回本层的规模（参数规模），那么这个返回值就会给本层的接收者 remain 不可能给最外层的接收者，虽然这里没有打印 remain的值，但是这里的remain和第一个列子中的remain，后面层数是有返回值的哦（下面例子就会体现），本例，返回到最外层时，list的本层规模为 [1,2,3] 最外层接收者接收到，然后打印出来，所以是[1,2,3] # 例5： def fullpermutation(list): if list is None: return None if len(list) == 1: return [list] res = [] pivot = list[0] remain = fullpermutation(list[1:]) print(remain) return list print(fullpermutation([1, 2, 3])) ''' 输出结果为： [[3]] [2, 3] [1, 2, 3] ''' 看上面的例子，这次我们是打印了 remain，因为返回的过程中，指向阻塞处（调用处）下面的代码，每次return list 即是 在本层返回 当前的参数规模，所以 remain 是能接收本层的返回值的，所以会打印 [[3]] ，[2, 3] ；最后 [1, 2, 3] 是最外层打印的 # 例6： def fullpermutation(list): if list is None: return None if len(list) == 1: return [list] res = [] pivot = list[0] remain = fullpermutation(list[1:]) print(remain) print(list) return list print(fullpermutation([1, 2, 3])) ''' 输出结果为： [[3]] [2, 3] [2, 3] [1, 2, 3] [1, 2, 3] '''这个，就是所有的融合；通过上面的代码我们来总结下return的返回值：最后一层遇到的return 需要执行 回的过程，此时的返回值 值会返回给最后的调用处的接收者；然后执行 阻塞处下面的代码时，如果又遇到return 这里的返回值，如果没有到达最外层，都是给本层的接收者！为什么要大费周章的讲这个，是因为我们在写递归时，往往不清楚return 要怎么写，已及它的返回值是什么？接下来就要看下return 如何解决问题的 请用递归完成一个字符串的反转，输入字符串“abcd”，完成翻转成“dcba” 除了递归，我们可以直接用字符串的切片来完成，如下，但是这里是要讲递归的思想，不体现方法优劣！ s="abcd" print(s[::-1])想一下递归的思路该怎么做？ 思路一：按照上面的例子，不断的划分子规模，我们选的是划分原字符串的规模，都是往后截取的，比如第一次参数s=“abcd” 我们取参数s[1:] ，不断调用函数，每次传入参数为：‘bcd’ ‘cd’ ‘d’ ，这样最后一层返回d 我们能拿到最后一个值，然后最后一个返回值d 加上 当前规模的第一个值，就完成了反转，具体代码如下： def str_reverse(s): if len(s) >>反转链表多种解法 有提到，这里不细说！  直到 回到最外层，起初的头结点，自然会指向None，最后返回 last_node即可  这才是 链表反转 递归的详细过程，果然和我开始理解的不一样，当初怎么都无法理解，直到用断点调试，才发现真正的过程，是这样，大家可以用断点调试下，看下代码的具体过程，下面是测试代码：
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def ReverseList(self, pHead):
if pHead is None:
return None
if pHead.next is None:
return pHead
last_node = self.ReverseList(pHead.next)
print(last_node.val)
pHead.next.next = pHead
pHead.next = None
return last_node
def print_list(self, node): # 打印测试
if node is None:
return None
while node:
print(node.val, end="")
node = node.next
print()
if __name__ == '__main__':
n1 = ListNode(1) # 依次实例5个结点
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n1.next = n2 # 依次将结点链接起来，形成一个链表
n2.next = n3
n3.next = n4
n4.next = n5
n5.next = None
obj = Solution()
print(obj.ReverseList(n1).val)
# obj.print_list(n1) # 1 2 3 4 5
# obj.print_list(obj.ReverseList(n1)) # 5 4 3 2 1
递归思路
思想： 1.找到当前这个值与上一个值的关系 2.找到程序的出口 有个明确的结束条件 3.假设当前功能已经完成 每次进入更深一层递归时，问题规模相比上次递归都应有所减少 递归思路： （1）找重复：看哪一部分是 实现函数的变化；每次进入更深一层递归时，问题规模相比上次递归都应有所减少 （2）找变化：变化的量应该作为参数 （3）找边界（出口）：终止条件 递归可以分为： （1）直接量+小规模子问题 （2）多个小规模子问题 （3） “切蛋糕”思维 （4）找递推公式，等价交换公式 二分法和递归 # 二分法一定是在排序好的数据里使用 lst = [33, 22, 44, 55, 66, 88, 77, 99, 101, 238, 345, 456, 567, 678, 789] n = 76 lst.sort() left = 0 right = len(lst) - 1 while left >打印f-e的数： def pri(f, e): if f > e: return else: print(f) return pri(f + 1, e) pri(1, 6) >>>求一个列表的和： def sum_lis(li, f): # 如果单独是传入一个列表，它体现不了变化 """ :param li: 传入一个列表 :param f: 列表起始位置 :return: 列表和 """ if f == len(li) - 1: # 表示起始位置也是结束位置，即只有一个元素 return li[f] return li[f] + sum_lis(li, f + 1) print(sum_lis([1, 2, 3, 4, 5], 0)) # 多引入一个 变化的参数，可以想到第一个元素加上剩下的元素，规模不断变小 # 需求:求 1+2+3+4........100 的和 num = 1 count = 0 while num >>需求：打印斐波那契数列 def fibo(num): # 参数是表示第n个斐波那契数，函数整体表示获取斐波那契数列中第n个数字的值 if num == 1 or num == 2: # 第一个和第二个都是1 return 1 # 返回1，出口 return fibo(num - 1) + fibo(num - 2) # 规律，后一项加上后两项，就等于斐波那契数列第n个数字的值 if __name__ == '__main__': list_num = [] # 创建一个空列表，开始 for i in range(1, 21): # 遍历1-20 list_num.append(fibo(i)) # 注意这里开始调用函数，获得一个斐波那契数字，将获取到的值填充到list_num print(list_num) # 最佳解法： def fei_bo(n): if n >> f(m,n)=f(n,m%n) >>>用递归实现列表排序： def ins(li, k): if k == 0: return # 对前K个元素进行排序 ins(li, k - 1) # 把位置K的元素插入到前面的部分 x = li[k] index = k - 1 while x >>需求：递归实现遍历目录 import os def get_alldirfile(source_path): # 定义一个函数获取用户输入的路径名下所有目录和文件 if not os.path.exists(source_path): # 判断用户输入的目录是否存在 return # 不存在，直接返回，结束该函数，找到一个出口 list_name = os.listdir(source_path) # lisdir获取所有目录，并全部放到一个列表中 for flie_dirname in list_name: # 遍历下所有的文件目录名 abs_path = os.path.join(source_path, flie_dirname) # 拼接成绝对路径 # 判断下一级是否是目录还是文件，是文件结束，是目录继续深入，直到是文件结束 if os.path.isfile(abs_path): # 是文件 print("file_path:%s" % (abs_path)) # 也可进行复制操作，open(abs_path,"w",encoding="utf-8") if os.path.isdir(abs_path): get_alldirfile(abs_path) # 递归函数 if __name__ == '__main__': path = r"F:\日语\快乐50音" get_alldirfile(path) # 优化 import os def file_get(file_path, n): list_file = os.listdir(file_path) for file in list_file: abs_file = os.path.join(file_path, file) if os.path.isdir(abs_file): print("\t" * n, file) file_get(abs_file, n + 1) else: print("\t" * n, file) file_get("D:\KuGou", 1) |
回来看下，代码输出的结果：5 4 3 2 1 00 1 2 3 4 5 （ 注意00这两个是在同一层空间哦） 
【本文地址】